﻿#ifndef __BELLMANFORD__
#define __BELLMANFORD__
//*********************** Bellman-Ford ****************************
//在一般情况下（存在负权边的情况），解决单源最短路径问题
//运行算法后，返回一个布尔值，false表明图中是否存在一个从源点可达的权值为负的回路
//若不存在这样的回路，则算法将产生最短路径及其权值
//运行时间为O（VE），其中，V为图的顶点个数，E为图的边的个数
#include <iostream>
#include <list>
#define MAX_NODE_NUM 100
#define MAX_ARC_NUM 200

struct graph{
	bool matrix[MAX_NODE_NUM][MAX_NODE_NUM];
	int node_num;
	int arc_num;
};

struct arc{
	char x;
	char y;
	int weight;
};

graph g;
arc g_arc[MAX_ARC_NUM];
int father[MAX_NODE_NUM];//父节点
int distance[MAX_NODE_NUM];//与源点的距离
char nodes[MAX_NODE_NUM];

int LocateNode(char c){
	int index = -1;
	for(int i = 0; i < g.node_num; ++i){
		if(nodes[i] == c){
			index = i;
			break;
		}
	}
	return index;
}

void CreateGraph(){
	for(int i = 0; i< g.node_num ;++i)
		for(int j = 0; j < g.node_num; ++j)
			g.matrix[i][j] = false;
	std::cout << "input node num :" ;
	std::cin >> g.node_num;
	for(int i = 0; i < g.node_num; ++i){
		std::cout << "input node [" << i+1 << "]'s lable:" ;
		std::cin >> nodes[i];
	}
	std::cout << std::endl << "input arc num :";
	std::cin >> g.arc_num;
	for(int i = 0; i < g.arc_num ; ++i){
		std::cout << "input arc and its weight:";
		std::cin >> g_arc[i].x >> g_arc[i].y >> g_arc[i].weight ;
		int x = LocateNode(g_arc[i].x),
			y = LocateNode(g_arc[i].y);
		g.matrix[x][y] = true;
	}
	/*g.node_num = 5;
	g.arc_num = 10;
	nodes[0] = 's';
	nodes[1] = 't';
	nodes[2] = 'x';
	nodes[3] = 'z';
	nodes[4] = 'y';
	g_arc[0].x = 's'; g_arc[0].y='t'; g_arc[0].weight = 6; g.matrix[0][1] = true;
	g_arc[1].x = 't'; g_arc[1].y='x'; g_arc[1].weight = 5; g.matrix[1][2] = true;
	g_arc[2].x = 'x'; g_arc[2].y='t'; g_arc[2].weight = -2; g.matrix[2][1] = true;
	g_arc[3].x = 't'; g_arc[3].y='z'; g_arc[3].weight = -4; g.matrix[1][3] = true;
	g_arc[4].x = 't'; g_arc[4].y='y'; g_arc[4].weight = 8; g.matrix[1][4] = true;
	g_arc[5].x = 'z'; g_arc[5].y='x'; g_arc[5].weight = 7; g.matrix[3][2] = true;
	g_arc[6].x = 'z'; g_arc[6].y='s'; g_arc[6].weight = 2; g.matrix[3][0] = true;
	g_arc[7].x = 'y'; g_arc[7].y='z'; g_arc[7].weight = 9; g.matrix[4][3] = true;
	g_arc[8].x = 'y'; g_arc[8].y='x'; g_arc[8].weight = -3; g.matrix[4][2] = true;
	g_arc[9].x = 's'; g_arc[9].y='y'; g_arc[9].weight = 7; g.matrix[0][4] = true;*/
}

void InitializeSingleSource(char c){
	for(int i =0; i < g.node_num; ++i){
		distance[i] = std::numeric_limits<int>::max();
		father[i] = i;
	}
	int index = LocateNode(c);
	distance[index] = 0;
}
void ShowPath(char);
//最短路径，最多存在v-1 条边。
//该算法从1 到v-1 ，遍历了每条边，进行“松弛”操作
bool BellmanFord(char source){
	InitializeSingleSource(source);
	for(int i = 1; i < g.node_num; ++i){
		for(int j = 0 ;j < g.arc_num; ++j){
			int x = LocateNode(g_arc[j].x),
				y = LocateNode(g_arc[j].y);
			if(distance[y] >  distance[x] + g_arc[j].weight){
				distance[y] = distance[x] + g_arc[j].weight;
				father[y] = x;
			}
		}
	}

	for(int i = 0; i < g.arc_num; ++i){
		int x = LocateNode(g_arc[i].x),
			y = LocateNode(g_arc[i].y);
		if(distance[y] >  distance[x] + g_arc[i].weight)
			return false;
	}
	return true;
}

void ShowPath(char destination){
	int d_index = LocateNode(destination);
	std::list<int> path;
	for(;;){
		path.push_front(d_index);
		if(d_index == father[d_index]) break;
		d_index = father[d_index];
	}
	std::list<int>::iterator it = path.begin();
	for(;;){
		if(it == path.end()) break;
		std::cout << nodes[*it++] <<" -> ";
	}
	std::cout << "end" << std::endl;
}

#endif